package structure.tree;

import java.util.LinkedList;
import java.util.Stack;

/**
 * java实现二叉树遍历
 * 前中后指的是根节点是在前中后那个位置，另外还有一个原则，这三种方式左节点都在右节点前
 * <p>
 * 参考博客：https://mp.weixin.qq.com/s/MlYtcR3I4dlAZuTM1Qo77A
 *
 * @author cuihao
 * @date 2018/2/27
 */
public class BinaryTree1 {


    // 最大深度
    public Integer maxDepth(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        int leftMaxDepth = maxDepth(treeNode.left);
        int rightMaxDepth = maxDepth(treeNode.right);
        return Math.max(leftMaxDepth, rightMaxDepth) + 1;
    }

    // 最小深度
    public Integer minDepth(TreeNode treeNode) {
        if (treeNode == null){
            return 0;
        }
        if (treeNode.left == null || treeNode.right == null) {
            return 1;
        }
        int leftMinDepth = minDepth(treeNode.left);
        int rightMinDepth = minDepth(treeNode.right);
        return Math.min(leftMinDepth, rightMinDepth) + 1;
    }

    // 全部节点个数
    public int numOfTree(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        int leftNum = numOfTree(treeNode.left);
        int rightNum = numOfTree(treeNode.right);
        return leftNum + rightNum + 1;
    }

    // 全部子节点个数
    public int numOfNoChildTree(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        if (treeNode.left == null && treeNode.right == null) {
            return 1;
        }
        int leftNum = numOfNoChildTree(treeNode.left);
        int rightNum = numOfNoChildTree(treeNode.right);
        return leftNum + rightNum;
    }


    // 按照值查找
    public TreeNode findByValue(TreeNode rootNode, Integer value) {
        TreeNode cur = rootNode;
        while (true) {
            if (value.equals(cur.value)) {
                return cur;
            } else if (value > cur.value) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
            if (cur == null) {
                return null;
            }
        }
    }

    // 按照值插入
    public void insert(TreeNode rootNode, Integer value) {
        TreeNode node = new TreeNode(value);
        if (rootNode == null) {
            rootNode = node;
        } else {
            TreeNode cur = rootNode;
            TreeNode parent = null;
            while (true) {
                if (value > cur.value) {
                    parent = cur;
                    cur = cur.right;
                    if (cur == null) {
                        parent.right = node;
                        break;
                    }
                } else if (value < cur.value) {
                    parent = cur;
                    cur = cur.left;
                    if (cur == null) {
                        parent.left = node;
                        break;
                    }
                } else {
                    break;
                }
            }
        }
    }

    // 广度遍历 - 假.层序遍历
    public void levelOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        LinkedList<TreeNode> queue = new LinkedList();
        queue.offer(node);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.println(cur.value);
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    // 深度遍历
    public void preDepth(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(node);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            System.out.println(cur.value);
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

    // 前序遍历 根在前
    public void preOrder(TreeNode node) {
        if (node != null) {
            System.out.println(node.value);
            preOrder(node.left);
            preOrder(node.right);

        }
    }

    // 中序遍历 根在中
    public void midOrder(TreeNode node) {
        if (node != null) {
            midOrder(node.left);
            System.out.println(node.value);
            midOrder(node.right);
        }
    }

    // 后序遍历 根在后
    public void lastOrder(TreeNode node) {
        if (node != null) {
            lastOrder(node.left);
            lastOrder(node.right);
            System.out.println(node.value);
        }
    }

    //    5
    //  1   8
    // 0 2 6 9
    private static class TreeNode {
        private Integer value;
        private TreeNode left;
        private TreeNode right;

        private TreeNode(Integer value) {
            this.value = value;
        }
    }
}